from typing import List


class Solution:
    _MOD = 10 ** 9 + 7

    def sumOfFlooredPairs(self, nums: List[int]) -> int:
        max_val = max(nums)

        # 计算每个数的出现次数
        count = [0] * (max_val + 1)
        for num in nums:
            count[num] += 1

        # 计算前缀频数和
        prefix = [0] * (max_val + 1)
        for i in range(1, max_val + 1):
            prefix[i] = prefix[i - 1] + count[i]

        ans = 0

        # 遍历每个出现的数
        for i in range(1, max_val + 1):
            if count[i] > 0:
                # 遍历该数每一个倍数区间的范围
                j = 1
                while i * j <= max_val:
                    ans = (ans + (prefix[min(max_val, i * j + i - 1)] - prefix[(i * j) - 1]) * count[i] * j) % self._MOD
                    j += 1

        return ans


if __name__ == "__main__":
    print(Solution().sumOfFlooredPairs(nums=[2, 5, 9]))  # 10
    print(Solution().sumOfFlooredPairs(nums=[7, 7, 7, 7, 7, 7, 7]))  # 49
